package leetbook.before_start;

import java.util.Arrays;

public class Solution5 {

    public static void main(String[] args) {
        int k = 2, n = 6;
        System.out.println(new Solution5().superEggDrop1(k,n));
    }

    public int superEggDrop_wrong(int k, int n) {
        //鸡蛋每次都有摔烂的可能，尽可能使用k-1个鸡蛋排除掉最多的选择，二分
        //用n代表剩余的可能楼层数
        for (int i = 1; i <= k-1; i++) { //用k-1个鸡蛋试错
            n = n-1; //试试中间的那个楼层
            n = (n&1)==0?(n>>1):(n>>1)+1; //如果n可以整除2则平分，若不能则需要测剩余更多的那一半
        }
        //k-1个鸡蛋壮烈殉国，剩余的可能性只能让剩下一个鸡蛋一个一个从下往上测试
        return n+k-1;
    }

    public int superEggDrop_overtime(int k, int n) {
        /**
         * 动态规划，dp[i,j]表示i个蛋j层楼的最少尝试次数
         * 第一个蛋总要扔出，如果选择从第l(1<=l<=j)层扔第一个蛋
         * 这个蛋如果碎了，那么剩余操作次数至少dp[i-1,l-1]
         * 如果这个鸡蛋没碎，剩余操作次数至少dp[i,j-l]
         * 所以选择从第j层楼扔出第一个鸡蛋的最少总操作次数在最坏情况下为Ml=max(dp[i-1,l-1],dp[i,j-l])+1
         * 那么怎样抛出第一个蛋才最好呢？就要从M1...Ml...Mj中选取最小者
         */
        int[][] dp = new int[k+1][n+1];
        for (int i = 1; i <= k; i++) {
            dp[i][1] = 1;
        }
        for (int i = 1; i <= n; i++) {
            dp[1][i] = i;
        }
        //初始化
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                int min = Integer.MAX_VALUE;
                for (int l = 1; l <= j; l++) {
                    min = Math.min(min,Math.max(dp[i-1][l-1],dp[i][j-l]));
                }
                dp[i][j] = min+1;
            }
        }
        return dp[k][n];
    }

    public int superEggDrop(int k, int n) {
        /**
         * 动态规划，dp[i,j]表示i个蛋j层楼的最少尝试次数
         * 第一个蛋总要扔出，如果选择从第l(1<=l<=j)层扔第一个蛋
         * 这个蛋如果碎了，那么剩余操作次数至少dp[i-1,l-1]
         * 如果这个鸡蛋没碎，剩余操作次数至少dp[i,j-l]
         * 所以选择从第j层楼扔出第一个鸡蛋的最少总操作次数在最坏情况下为Ml=max(dp[i-1,l-1],dp[i,j-l])+1
         * 那么怎样抛出第一个蛋才最好呢？随着l增加，dp[i-1,l-1]不减，dp[i,j-l]不增，找一个均衡点，即二者相减值的符号发生变化的点
         */
        int[][] dp = new int[k+1][n+1];
        for (int i = 1; i <= k; i++) {
            dp[i][1] = 1;
        }
        for (int i = 1; i <= n; i++) {
            dp[1][i] = i;
        }
        //初始化
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = findMin(i,j,dp)+1;
            }
        }
        return dp[k][n];
    }

    public int findMin(int i, int j, int[][] dp){
        //二分查找dp[i-1,l-1]和dp[i,j-l]在l=1...l中相差最小位置
        //dp[i-1,l-1]增，dp[i,j-l]减
        int left = 1, right = j;
        while (left<=right){
            int mid = (left+right)>>1;
            if(dp[i-1][mid-1]<dp[i][j-mid]) left = mid + 1;
            else if(dp[i-1][mid-1]>dp[i][j-mid]) right = mid - 1;
            else return dp[i-1][mid-1];
        }
        //如果没有相等的点，结束时right所指是最后一个dp[i-1][mid-1]>dp[i][j-mid]的位置
        return Math.min(dp[i-1][right],dp[i][j-right]);
    }

    public int superEggDrop1(int k, int n) {
        /**
         * 动态规划，dp[i,j]表示i个蛋j层楼的最少尝试次数
         * 第一个蛋总要扔出，如果选择从第l(1<=l<=j)层扔第一个蛋
         * 这个蛋如果碎了，那么剩余操作次数至少dp[i-1,l-1]
         * 如果这个鸡蛋没碎，剩余操作次数至少dp[i,j-l]
         * 所以选择从第j层楼扔出第一个鸡蛋的最少总操作次数在最坏情况下为Ml=max(dp[i-1,l-1],dp[i,j-l])+1
         * 那么怎样抛出第一个蛋才最好呢？随着l增加，dp[i-1,l-1]不减，dp[i,j-l]不增，找一个均衡点，即二者相减值的符号发生变化的点
         */
        int[][] dp = new int[k+1][n+1];
        for (int i = 1; i <= k; i++) {
            dp[i][1] = 1;
        }
        for (int i = 1; i <= n; i++) {
            dp[1][i] = i;
        }
        //初始化
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                int left = 1, right = j, mid = 0;
                while (left<=right){
                    mid = (left+right)>>1;
                    if(dp[i-1][mid-1]<dp[i][j-mid]) left = mid + 1;
                    else if(dp[i-1][mid-1]>dp[i][j-mid]) right = mid - 1;
                    else break;
                }
                if(dp[i-1][mid-1]==dp[i][j-mid]) dp[i][j] = dp[i-1][mid-1]+1;
                else dp[i][j] = Math.min(dp[i-1][right],dp[i][j-right])+1;
            }
        }
        return dp[k][n];
    }
}
